package com.yanceysong.codetop.s31_s40;

import com.yanceysong.common.TreeNode;


public class S32_Hard_124_二叉树中的最大路径和 {
    /**
     * 全局最大路径和（可能在任何节点作为“拐点”出现）
     */
    private int globalMaxPathSum = Integer.MIN_VALUE;

    /**
     * S32_Hard_124_二叉树中的最大路径和
     * <p>
     * 题目链接: <a href="https://leetcode.cn/problems/binary-tree-maximum-path-sum/">...</a>
     * <p>
     * 【题目描述】
     * 给你一个二叉树的根节点 root ，路径 被定义为一条从树中任意节点出发、到达任意节点的序列。
     * 序列中相邻节点之间必须存在一条边。同一个节点 在一条路径序列中 至多出现一次 。路径 至少包含一个 节点，且 不一定经过根节点。
     * 路径和 是路径中各节点值之和。请返回该二叉树中 任意路径 的 最大路径和。
     * <p>
     * 【示例 1】
     * 输入: root = [1,2,3]
     * .           1
     * .         /   \
     * .        2     3
     * 输出: 6  （路径 2 -> 1 -> 3）
     * <p>
     * 【示例 2】
     * 输入: root = [-10,9,20,null,null,15,7]
     * .              -10
     * .             /    \
     * .            9      20
     * .                  /  \
     * .                15    7
     * 输出: 42 （路径 15 -> 20 -> 7）
     * <p>
     * 【示例 3】
     * 输入: root = [5,4,8,11,null,13,4,7,2,null,null,null,1]
     * .               5
     * .             /   \
     * .            4     8
     * .           /     / \
     * .         11     13  4
     * .        /  \          \
     * .       7    2          1
     * 输出: 48 （路径 7 -> 11 -> 4 -> 5 -> 8 -> 13）
     * <p>
     * 【关键洞察】
     * 1. “最大路径”可以在某个节点处拐弯（经过它的左右子树），也可以是纯向下的一条链。
     * 2. 对于任意节点，我们希望知道：从它向下（只能选左或右之一）能获得的“最大单侧贡献”。
     * 3. 若在该节点作为“最高点（拐点）”，路径和 = 节点值 + 左最大贡献(>=0) + 右最大贡献(>=0)。
     * 4. 全局答案是遍历所有节点时出现的上述“拐点路径和”的最大值。
     * 5. 递归返回给父节点的值只能是：节点值 + max(左贡献, 右贡献) （因为父节点只能接一条链，不能同时接左右两边）。
     * <p>
     * 【算法图解 - 单个节点的三种相关值】
     * 对某个节点 N：
     * .  ┌─────────────────────────────────────────┐
     * .  │ 1) 左子树最大向下贡献  leftGain (若<0则视为0) │
     * .  │ 2) 右子树最大向下贡献  rightGain(若<0则视为0) │
     * .  │ 3) 以当前节点为“拐点”的路径和：               │
     * .  │        currentPathSum = N.val + leftGain + rightGain │
     * .  └─────────────────────────────────────────┘
     * 向父节点返回： N.val + max(leftGain, rightGain)
     * 全局维护：globalMaxPathSum = max(globalMaxPathSum, currentPathSum)
     * <p>
     * 【ASCII 递归示意】 (负贡献剪枝概念)
     * .           (N)
     * .          /   \
     * .      (A)      (B)
     * .      / \      / \
     * .     ... ...  ... ...
     * <p>
     * 递归得到 A 向下最大贡献 = aGain
     * B 向下最大贡献 = bGain
     * 如果 aGain < 0 则抛弃，视为 0；bGain 同理。
     * currentPathSum = N.val + max(aGain,0) + max(bGain,0)
     * 返回给父节点的贡献 = N.val + max(max(aGain,0), max(bGain,0))
     * <p>
     * 【时间复杂度】O(N)  每个节点访问一次
     * 【空间复杂度】O(H)  递归栈高度（H为树高，最坏O(N)，平均平衡树为O(logN)）
     * <p>
     * 【边界注意】
     * 1. 节点值可以为负；若所有节点都是负数，答案是其中最大值（靠 max(global, currentPathSum) 实现）。
     * 2. 不能为了减少路径和而“跳过”某个单个节点（路径必须由真实相邻节点组成）。
     */
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0; // 按题意至少有一个节点，这里兜底
        }
        computeMaxGain(root);
        return globalMaxPathSum;
    }

    /**
     * 递归函数：计算“从当前节点向下的最大单侧贡献值”
     * 含义：当前节点选取一条（左 或 右）向下的链，使得 节点值 + 链上节点值 之和最大。
     * 同时在回溯过程中，更新全局最大路径和（允许当前节点把左右正贡献都作为拐点连接起来）。
     * <p>
     * 变量命名说明：
     * leftGain / rightGain: 左、右子树向下的最大贡献（若为负则置0表示不取该方向）。
     * currentPathSum: 以当前节点为最高点（可连接左右）的路径和。
     *
     * @param node 当前节点
     * @return 返回给父节点的“最大单侧向下贡献”
     */
    private int computeMaxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 递归计算左右最大向下贡献；若贡献为负，直接丢弃（视为0）
        int leftGain = Math.max(computeMaxGain(node.left), 0);
        int rightGain = Math.max(computeMaxGain(node.right), 0);

        // 以当前节点为“拐点”时，能形成的路径和（左右都可取，只取>=0的部分）
        int currentPathSum = node.val + leftGain + rightGain;

        // 尝试更新全局最大值
        if (currentPathSum > globalMaxPathSum) {
            globalMaxPathSum = currentPathSum;
        }

        // 返回“当前节点作为一条向上延伸链的端点”时，能提供给父节点的最大单侧贡献
        return node.val + Math.max(leftGain, rightGain);
    }

    public static void main(String[] args) {
        S32_Hard_124_二叉树中的最大路径和 solution = new S32_Hard_124_二叉树中的最大路径和();

        System.out.println("=== 二叉树中的最大路径和 测试开始 ===\n");

        testExample1(solution);
        testExample2(solution);
        testExample3(solution);
        testAllNegative(solution);
        testSingleNode(solution);
        testMixedStructure(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 示例1：简单完全二叉树
     */
    private static void testExample1(S32_Hard_124_二叉树中的最大路径和 solution) {
        System.out.println("--- 测试1: 示例1 [1,2,3] ---");
        TreeNode root = buildTree(new Integer[]{1, 2, 3});
        int ans = solution.maxPathSum(root);
        System.out.println("结果: " + ans + " (期望: 6)");
        assert ans == 6 : "测试1失败";
        reset(solution);
    }

    /**
     * 示例2：题干经典案例
     */
    private static void testExample2(S32_Hard_124_二叉树中的最大路径和 solution) {
        System.out.println("--- 测试2: 示例2 [-10,9,20,null,null,15,7] ---");
        TreeNode root = buildTree(new Integer[]{-10, 9, 20, null, null, 15, 7});
        int ans = solution.maxPathSum(root);
        System.out.println("结果: " + ans + " (期望: 42)");
        assert ans == 42 : "测试2失败";
        reset(solution);
    }

    /**
     * 示例3：更复杂结构
     */
    private static void testExample3(S32_Hard_124_二叉树中的最大路径和 solution) {
        System.out.println("--- 测试3: 示例3 [5,4,8,11,null,13,4,7,2,null,null,null,1] ---");
        TreeNode root = buildTree(new Integer[]{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1});
        int ans = solution.maxPathSum(root);
        System.out.println("结果: " + ans + " (期望: 48)");
        assert ans == 48 : "测试3失败";
        reset(solution);
    }

    /**
     * 所有节点为负数，应该选取单个最大节点
     */
    private static void testAllNegative(S32_Hard_124_二叉树中的最大路径和 solution) {
        System.out.println("--- 测试4: 全为负数 [-3,-2,-5] ---");
        TreeNode root = buildTree(new Integer[]{-3, -2, -5});
        int ans = solution.maxPathSum(root);
        System.out.println("结果: " + ans + " (期望: -2)");
        assert ans == -2 : "测试4失败";
        reset(solution);
    }

    /**
     * 单节点（负）
     */
    private static void testSingleNode(S32_Hard_124_二叉树中的最大路径和 solution) {
        System.out.println("--- 测试5: 单节点 [-3] ---");
        TreeNode root = buildTree(new Integer[]{-3});
        int ans = solution.maxPathSum(root);
        System.out.println("结果: " + ans + " (期望: -3)");
        assert ans == -3 : "测试5失败";
        reset(solution);
    }

    /**
     * 混合结构，包含一侧为负的情况
     */
    private static void testMixedStructure(S32_Hard_124_二叉树中的最大路径和 solution) {
        System.out.println("--- 测试6: 混合结构 [2,-1] ---");
        TreeNode root = buildTree(new Integer[]{2, -1});
        int ans = solution.maxPathSum(root);
        System.out.println("结果: " + ans + " (期望: 2)");
        assert ans == 2 : "测试6失败";
        reset(solution);
    }

    /**
     * 按层序（数组表示）构建二叉树，null 表示缺失节点。
     *
     * @param arr 层序数组
     */
    private static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0) return null;
        TreeNode[] nodes = new TreeNode[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != null) nodes[i] = new TreeNode(arr[i]);
        }
        for (int i = 0, j = 1; j < arr.length; i++) {
            if (nodes[i] != null) {
                if (j < arr.length) nodes[i].left = nodes[j++];
                if (j < arr.length) nodes[i].right = nodes[j++];
            }
        }
        return nodes[0];
    }

    /**
     * 重置内部状态以便复用同一个 solution 实例
     */
    private static void reset(S32_Hard_124_二叉树中的最大路径和 solution) {
        solution.globalMaxPathSum = Integer.MIN_VALUE;
    }
}
